#ifndef _GRAPH_H_
#define _GRAPH_H_

#include "Object.h"
#include "SharedPointer.h"
#include "DynamicArray.h"
#include "Exception.h"
#include "LinkQueue.h"
#include "LinkStack.h"
#include "Sort.h"

namespace MySTL
{

template < typename E >
struct Edge : public Object
{
	E data;
	int begin;
	int end;

	Edge(int begin = -1, int end = -1);
	Edge(const E& value, int begin, int end);

	bool operator <(const Edge& obj) const;
	bool operator >(const Edge& obj) const;
};

template < typename V, typename E >
class Graph : public Object
{
public:
	Graph() {}

	virtual V& getVertex(int n) = 0;
	virtual const V& getVertex(int n) const = 0;
	virtual bool getVertex(int n, V& value) const = 0;
	virtual bool setVertex(int n, const V& value) = 0;
	virtual SharedPointer< Array<int> > getAdjacent(int n) const = 0;
	virtual E& getEdge(int i, int j) = 0;
	virtual const E& getEdge(int i, int j) const = 0;
	virtual bool getEdge(int i, int j, E& value) const = 0;
	virtual bool setEdge(int i, int j, const E& value) = 0;
	virtual bool removeEdge(int i, int j) = 0;
	virtual int VCount() const = 0;
	virtual int ECount() const = 0;
	virtual int IDegree(int n) const = 0;
	virtual int ODegree(int n) const = 0;
	virtual int TDegree(int n) const;
	virtual bool isAdjacent(int i, int j) const = 0;
	virtual bool asUndirected() const;

	virtual SharedPointer< Array<int> > BFS(int n) const;
	virtual SharedPointer< Array<int> > DFS(int n) const;

	virtual SharedPointer< Array<Edge<E>> > prim(bool min = true) const;
	virtual SharedPointer< Array<Edge<E>> > kruskal(bool min = true) const;

	virtual bool dijkstra(int n, SharedPointer< Array<E> >* dist_array, SharedPointer< Array<int> >* path_array, bool min = true) const;
	virtual SharedPointer< Array<int> > dijkstra(int i, int j, bool min = true) const;

protected:
	Graph(const Graph& obj);
	Graph& operator =(const Graph& obj);

	int getPreIndex(Array<E>& array, int n) const;
};

template < typename T >
static DynamicArray<T>* QueueToArray(LinkQueue<T>& queue);

template < typename E >
Edge<E>::Edge(int begin, int end)
{
	this->begin = begin;
	this->end = end;
}

template < typename E >
Edge<E>::Edge(const E& value, int begin, int end) : data(value)
{
	this->begin = begin;
	this->end = end;
}

template < typename E >
bool Edge<E>::operator <(const Edge& obj) const
{
	return data < obj.data;
}

template < typename E >
bool Edge<E>::operator >(const Edge& obj) const
{
	return data > obj.data;
}

template < typename V, typename E >
int Graph<V, E>::TDegree(int n) const
{
	return IDegree(n) + ODegree(n);
}

template < typename V, typename E >
bool Graph<V, E>::asUndirected() const
{
	bool ret = true;

	for (int i = 0; ret && i < VCount(); ++i)
	{
		for (int j = i + 1; ret && (j < VCount()); ++j)
		{
			if (isAdjacent(i, j))
			{
				ret = isAdjacent(j, i) && (getEdge(i, j) == getEdge(j, i));
			}
		}
	}

	return ret;
}

template < typename V, typename E >
SharedPointer< Array<int> > Graph<V, E>::BFS(int n) const
{
	Array<int>* ret = NULL;

	if (n >= 0 && n < VCount())
	{
		DynamicArray<bool> flag(VCount());
		LinkQueue<int> queue;
		LinkQueue<int> ret_queue;

		for (int i = 0; i < flag.length(); ++i)
		{
			flag[i] = false;
		}

		queue.enqueue(n);

		while (queue.length() > 0)
		{
			int vi = queue.dequeue();

			if (false == flag[vi])
			{
				flag[vi] = true;
				ret_queue.enqueue(vi);

				SharedPointer< Array<int> > adjacent = getAdjacent(vi);
				if (!adjacent.isNull())
				{
					for (int i = 0; i < adjacent->length(); ++i)
					{
						queue.enqueue((*adjacent)[i]);
					}
				}
			}
		}

		ret = QueueToArray(ret_queue);
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in SharedPointer< Array<int> > Graph<V, E>::BFS(int n) const");
	}

	return ret;
}

template < typename V, typename E >
SharedPointer< Array<int> > Graph<V, E>::DFS(int n) const
{
	Array<int>* ret = NULL;

	if (n >= 0 && n < VCount())
	{
		DynamicArray<bool> flag(VCount());
		LinkStack<int> stack;
		LinkQueue<int> ret_queue;

		for (int i = 0; i < flag.length(); ++i)
		{
			flag[i] = false;
		}

		stack.push(n);

		while (stack.length() > 0)
		{
			int vi = stack.pop();

			if (false == flag[vi])
			{
				flag[vi] = true;
				ret_queue.enqueue(vi);

				SharedPointer< Array<int> > adjacent = getAdjacent(vi);
				if (!adjacent.isNull())
				{
					for (int i = adjacent->length() - 1; i >= 0; --i)
					{
						stack.push((*adjacent)[i]);
					}
				}
			}
		}

		ret = QueueToArray(ret_queue);
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in SharedPointer< Array<int> > Graph<V, E>::DFS(int n) const");
	}

	return ret;
}

template < typename V, typename E >
SharedPointer< Array<Edge<E>> > Graph<V, E>::prim(bool min) const
{
	Array< Edge<E> >* ret = NULL;

	if (VCount() > 0 && asUndirected())
	{
		DynamicArray<bool> flag(VCount());
		DynamicArray<E> cost(VCount());
		DynamicArray<int> adjVex(VCount());
		LinkQueue< Edge<E> > queue;

		for (int i = 0; i < VCount(); ++i)
		{
			flag[i] = false;
			adjVex[i] = -1;
		}

		int choose = 0;

		while (choose >= 0)
		{
			flag[choose] = true;

			SharedPointer< Array<int> > adjacent = getAdjacent(choose);
			if (!adjacent.isNull())
			{
				for (int i = 0; i < adjacent->length(); ++i)
				{
					int v = (*adjacent)[i];
					if (!flag[v])
					{
						const E& e = getEdge(choose, v);
						if ((adjVex[v] == -1) || (min ? e < cost[v] : e > cost[v]))
						{
							cost[v] = e;
							adjVex[v] = choose;
						}
					}
				}
			}
			else
				break;

			choose = -1;
			for (int i = 0; i < cost.length(); ++i)
			{
				if (!flag[i] && (adjVex[i] != -1) && ((choose == -1) || (min ? cost[i] < cost[choose] : cost[i] > cost[choose])))
				{
					choose = i;
				}
			}

			if (choose >= 0)
			{
				queue.enqueue(Edge<E>(cost[choose], adjVex[choose], choose));
			}
		}

		if (queue.length() == VCount() - 1)
		{
			ret = QueueToArray(queue);
		}
	}

	return ret;
}

template < typename V, typename E >
SharedPointer< Array<Edge<E>> > Graph<V, E>::kruskal(bool min) const
{
	Array< Edge<E> >* ret = NULL;

	int edge_count = ECount();
	if (VCount() > 0 && asUndirected() && edge_count >= 2)
	{
		DynamicArray< Edge<E> > edges(edge_count / 2);
		DynamicArray<int> pre(VCount());
		LinkQueue< Edge<E> > queue;

		for (int i = 0, count = 0; i < VCount(); ++i)
		{
			for (int j = i + 1; j < VCount(); ++j)
			{
				if (isAdjacent(i, j))
				{
					edges[count++] = Edge<E>(getEdge(i, j), i, j);
				}
			}
		}
		Sort::shell<Edge<E>>(edges, min ? Sort::Min2Max : Sort::Max2Min);
		for (int i = 0; i < VCount(); ++i)
		{
			pre[i] = -1;
		}

		for (int i = 0; (i < edges.length()) && (queue.length() < VCount() - 1); ++i)
		{
			int begin = getPreIndex(pre, edges[i].begin);
			int end = getPreIndex(pre, edges[i].end);
			if (begin != end)
			{
				pre[end] = begin;
				queue.enqueue(edges[i]);
			}
		}

		if (queue.length() == VCount() - 1)
		{
			ret = QueueToArray(queue);
		}
	}

	return ret;
}

template < typename V, typename E >
bool Graph<V, E>::dijkstra(int n, SharedPointer< Array<E> >* dist_array, SharedPointer< Array<int> >* path_array, bool min) const
{
	bool ret = (n >= 0) && (n < VCount());

	if (ret)
	{
		DynamicArray<E>* d = new DynamicArray<E>(VCount());
		if (NULL != d)
		{
			DynamicArray<int>* p = new DynamicArray<E>(VCount());
			if (NULL != p)
			{
				DynamicArray<E>& dist = *d;
				DynamicArray<int>& path = *p;
				DynamicArray<bool> flag(VCount());
				for (int i = 0; i < VCount(); ++i)
				{
					path[i] = -1;
					flag[i] = false;
				}

				int curr = n;

				while (curr != -1)
				{
					flag[curr] = true;
					SharedPointer< Array<int> > adjacent = getAdjacent(curr);

					if (!adjacent.isNull())
					{
						for (int i = 0; i < adjacent->length(); ++i)
						{
							int next = (*adjacent)[i];
							int edge = getEdge(curr, next);
							if ((path[next] == -1) || (min ? (dist[curr] + edge < dist[next]) : (dist[curr] + edge > dist[next])))
							{
								dist[next] = (curr != n) ? (dist[curr] + edge) : edge;
								path[next] = curr;
							}
						}
					}

					curr = -1;
					for (int i = 0; i < VCount(); ++i)
					{
						if ((flag[i] == false) && (path[i] != -1) && ((curr == -1) || (min ? (dist[i] < dist[curr]) : (dist[i] > dist[curr]))))
						{
							curr = i;
						}
					}
				}

				if (dist_array)
					*dist_array = &dist;
				else
					delete &dist;

				if (path_array)
					*path_array = &path;
				else
					delete &path;
			}
			else
			{
				THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory in Graph<V, E>::dijkstra");
			}
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory in Graph<V, E>::dijkstra");
		}
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in bool Graph<V, E>::dijkstra(int n, SharedPointer< Array<E> >* dist, SharedPointer< Array<int> >* path, bool min) const");
	}

	return ret;
}

template < typename V, typename E >
SharedPointer< Array<int> > Graph<V, E>::dijkstra(int i, int j, bool min) const
{
	SharedPointer< Array<int> > path;
	bool result = dijkstra(i, NULL, &path, min);
	SharedPointer< Array<int> > ret;

	if (result)
	{
		LinkStack<int> stack;
		LinkQueue<int> queue;

		stack.push(j);

		int k = j;
		while ((*path)[k] != -1)
		{
			stack.push((*path)[k]);
			k = (*path)[k];
		}
		stack.push(i);

		while (stack.length() > 0)
		{
			queue.enqueue(stack.pop());
		}

		if (queue.length() >= 2)
		{
			ret = QueueToArray(queue);
		}
	}

	return ret;
}

template < typename V, typename E >
int Graph<V, E>::getPreIndex(Array<E>& array, int n) const
{
	while (array[n] != -1)
	{
		n = array[n];
	}

	return n;
}

template < typename T >
DynamicArray<T>* QueueToArray(LinkQueue<T>& queue)
{
	DynamicArray<T>* ret = new DynamicArray<T>(queue.length());

	if (NULL != ret)
	{
		int i = 0;
		while (queue.length() > 0)
		{
			(*ret)[i++] = queue.dequeue();
		}
	}
	else
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create Array in DynamicArray<T>* Graph<V, E>::QueueToArray(LinkQueue<T>& queue)");
	}

	return ret;
}

}

#endif